//https://leetcode.cn/problems/satisfiability-of-equality-equations/submissions/583039580/

class Solution {
public:
    vector<int> same; // 并查集，用于记录每个字符的根节点（所属组）

    // 并查集查找操作（路径压缩优化）
    // 找到字符 ch 所在集合的根节点
    int find(int ch) {
        if (same[ch] == ch) return ch; // 如果 ch 是根节点，直接返回
        return same[ch] = find(same[ch]); // 路径压缩
    }

    // 并查集合并操作
    // 将字符 cha 和 chb 合并到同一集合
    void merge(int cha, int chb) {
        same[find(cha)] = find(chb); // cha 的根节点指向 chb 的根节点
    }

    // 主函数：判断给定的等式和不等式是否能同时成立
    bool equationsPossible(vector<string>& equations) {
        same.resize(26); // 初始化并查集大小（26个小写字母）
        for (int i = 0; i < 26; i++) same[i] = i; // 每个字母初始为独立的集合

        // 第一遍：处理所有等式，将相等的字符合并到同一集合
        for (string s : equations) {
            if (s[1] == '=') {
                // 如果是相等关系（"=="），合并两字符
                merge(s[0] - 'a', s[3] - 'a');
            }
        }

        // 第二遍：处理所有不等式，检查是否有冲突
        for (string s : equations) {
            if (s[1] == '!') {
                // 如果是不等关系（"!="），检查两字符是否属于同一集合
                if (find(s[0] - 'a') == find(s[3] - 'a')) {
                    return false; // 冲突，返回 false
                }
            }
        }

        return true; // 所有条件满足，返回 true
    }
};
